package com.future;

import java.util.Arrays;

/**
 * Description: 689. 三个无重叠子数组的最大和(大厂刷题班22)
 *
 * @author weiruibai.vendor
 * Date: 2022/7/12 14:47
 */
public class Solution_689 {

    public static void main(String[] args) {
        int[] nums = new int[]{1, 2, 1, 2, 6, 7, 5, 10};
        int k = 2;
       /* nums = new int[]
                {9, 2, -10, 2, 6, 7, 5, 10, -14, 10, 3, 1};
        k = 3;*/
        /*nums = new int[]{7, 13, 20, 19, 19, 2, 10, 1, 1, 19};
        k = 3;*/

      /*  nums = new int[]{17, 9, 3, 2, 7, 10, 20, 1, 13, 4, 5, 16, 4, 1, 17, 6, 4, 19, 8, 3};
        k = 4;// [3,8,14]*/
        System.out.println(Arrays.toString(maxSumOfThreeSubarrays(nums, k)));
    }

    /**
     * 过程可参考img/Solution_689.png
     *
     * @param nums
     * @param k
     * @return
     */
    public static int[] maxSumOfThreeSubarrays(int[] nums, int k) {
        int N = nums.length;
        int[] ans = new int[3];
        if (N / k < 3) {
            return ans;
        }
        int[] sum = new int[N];
        sum[0] = nums[0];
        for (int i = 1; i < N; i++) {
            sum[i] = sum[i - 1] + nums[i];
        }
        int preMaxSum = Integer.MIN_VALUE;
        int leftMaxSum = Integer.MIN_VALUE;
        int leftIndex = 0;
        int mL = k, mR = 2 * k - 1;
        /**
         * 思路：突破口是先固定中间范围，mid={k,N-k-1}
         * {0...k-1}{k...N-k-1}{N-k,N}
         * 1、当取mid={k,k+1,..,2*k-1}时，left={0,1,...,k-1},right={2*k,2*k+1,...,3*k-1}
         * 2、当取mid={k+1,k+2,..,2*k}时，left={1,2,...,k},right={2*k+1,2*k+2,...,3*k}
         * ...
         *
         * 注意：注意边界！！
         */
        for (; mR < N - k; mL++, mR++) {
            // 1、计算左边
            int tmpLeftVal = sum[mL - 1];
            if (mL - k - 1 >= 0) {
                /**
                 * 第一次，不会走这部分
                 */
                tmpLeftVal -= sum[mL - k - 1];
            }
            if (tmpLeftVal > leftMaxSum) {
                leftMaxSum = tmpLeftVal;
                leftIndex = mL - k;
            }
            // 计算中间
            int midSum = sum[mR] - sum[mL - 1];
            // 计算右边
            int rightMaxSum = Integer.MIN_VALUE;
            int rightIndex = -1;
            int rL = mR + 1, rR = rL + k - 1;
            for (; rR < N; rL++, rR++) {
                int tmpRightSum = sum[rR] - sum[rL - 1];
                if (tmpRightSum > rightMaxSum) {
                    rightMaxSum = tmpRightSum;
                    rightIndex = rL;
                }
            }
            int tmpSum;
            if ((tmpSum = leftMaxSum + midSum + rightMaxSum) > preMaxSum) {
                preMaxSum = tmpSum;
                ans[0] = leftIndex;
                ans[1] = mL;
                ans[2] = rightIndex;
            }
        }
        return ans;
    }

}
